import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:串联所有单词的子串
 * User: bjc
 * Date: 2025-11-13
 * Time: 09:55
 */
public class Test07_findSubstring {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int wordLength = words[0].length();
        int totalLength = wordLength * words.length;
        if(s.length() < totalLength) return list; //子串比主串长，直接返回空集合
        HashMap<String,Integer> map_w = new HashMap<>();//String表示单词，Integer表示单词出现的次数
        for (String word : words) {
            map_w.put(word,map_w.getOrDefault(word,0)+1); //统计单词出现的次数
        }
        for(int i = 0;i < wordLength;i++){
            HashMap<String,Integer> map_t = new HashMap<>();
            for(int left = i,right = i,count = 0;right <= s.length() - wordLength;right += wordLength){
                String in = s.substring(right,right + wordLength);
                //进窗口
                map_t.put(in,map_t.getOrDefault(in,0)+1);
                if(map_t.get(in) <= map_w.getOrDefault(in,0) ){
                    count++;
                }
                //判断是否出窗口
                if(right - left + 1 > totalLength){
                    String out = s.substring(left,left + wordLength);
                    if(map_t.get(out) <= map_w.getOrDefault(out,0)){
                        count--;
                    }
                    map_t.put(out,map_t.get(out)-1);
                    left += wordLength;
                }
                //更新结果
                if(count == words.length){
                    list.add(left);
                }
            }
        }
        return list;
    }
}
